home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / ptv2n1.arc / L3.C < prev    next >
Text File  |  1991-03-26  |  1KB  |  47 lines
  1. /* Finds and returns the greatest common divisor of two integers.
  2.    Uses Euclid's Algorithm: divides the larger integer by the
  3.    smaller; if the remainder is 0, the smaller integer is the gcd,
  4.    otherwise the smaller integer becomes the larger integer, the
  5.    remainder becomes the smaller integer, and the process is
  6.    repeated. */
  7.  
  8. static unsigned int gcd_recurs(unsigned int, unsigned int);
  9.  
  10. unsigned int gcd(unsigned int int1, unsigned int int2) {
  11.    unsigned int temp;
  12.  
  13.    /* If the two integers are the same, that's the gcd and we're
  14.       done */
  15.    if (int1 == int2) {
  16.       return(int1);
  17.    }
  18.  
  19.    /* Swap if necessary to make sure that int1 >= int2 */
  20.    if (int1 < int2) {
  21.       temp = int1;
  22.       int1 = int2;
  23.       int2 = temp;
  24.    }
  25.  
  26.    /* Now call the recursive form of the function, which assumes
  27.       that the first parameter is the larger of the two */
  28.    return(gcd_recurs(int1, int2));
  29. }
  30.  
  31. static unsigned int gcd_recurs(unsigned int larger_int,
  32.       unsigned int smaller_int)
  33. {
  34.    int temp;
  35.  
  36.    /* If the remainder of larger_int divided by smaller_int is 0,
  37.       then smaller_int is the gcd */
  38.    if ((temp = larger_int % smaller_int) == 0) {
  39.       return(smaller_int);
  40.    }
  41.  
  42.    /* Make smaller_int the larger integer and the remainder the
  43.       smaller integer, and call this function recursively to
  44.       continue the process */
  45.    return(gcd_recurs(smaller_int, temp));
  46. }
  47.